package leetcode;

import java.util.HashMap;

public class Lc2707 {


    private int ans;
    HashMap<String, Integer> map = new HashMap<>();
    //递归法-------------会超时
    public int minExtraChar(String s, String[] dictionary) {

        ans = s.length();
        getAns(s, dictionary);
        return ans;
    }

    private void getAns(String s, String[] dictionary) {
        if (ans == 0)
            return;

        if (map.containsKey(s))
            return;
        for (int i = 0; i < dictionary.length; i++) {
            if (s.contains(dictionary[i])) {
                getAns(s.replaceFirst(dictionary[i], "-"), dictionary);
            }
            if (ans == 0)
                return;
        }

        ans = Math.min(ans, s.replace("-", "").length());
        map.put(s, ans);
    }


    public static void main(String[] args) {
        Lc2707 lc2707 = new Lc2707();
        String s = "octncmdbgnxapjoqlofuzypthlytkmchayflwky";
        String[] d = {"m","its","imaby","pa","ijmnvj","k","mhka","n","y","nc","wq","p","mjqqa","ht","dfoa","yqa","kk","pixq","ixsdln","rh","dwl","dbgnxa","kmpfz","nhxjm","wg","wky","oct","og","uhin","zxb","qz","tpf","hlrc","j","l","tew","xbn","a","uzypt","uvln","mchay","onnbi","hlytk","pjoqlo","dxsjr","u","uj"};
        System.out.println(lc2707.minExtraChar(s,d));
    }


}
